package leetcode.editor.cn;
 
/**
 * 比特位计数
 * @author qulq
 * @date 2024-07-13 16:11:36
 */
public class T338_CountingBits{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new T338_CountingBits().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] countBits(int n) {
		// -(170) = 10101010
		// -(85) = 1010101, 往右移一位（除2）+ 最后一位是0或1
		// dp[i]: 表示i的二进制中有多少个1
		// dp[i] = dp[i>>1] + (i % 2)
		// dp[0] = 0
		int[] dp = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			dp[i] = dp[i >> 1] + (i % 2);
		}
		return dp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}